Asymptotic Equipartition Property

Convergence of Random Variable

The sequence $ X_1, X_2, \dots$ converges to $ X$ if:

• In probability:

$$ \forall \epsilon > 0, P[|X_n - X| > \epsilon ] \to 0 $$

• In mean square:

$$ E[(X_n - X)^2] \to 0 $$

• Almost surely:

$$ P[\lim_{n \to \infty} X_n = X] = 1 $$

Asymptotic Equipartition Property Theorem

If $ X_1, X_2, \dots $ are i.i.d. $ \sim p(x)$, then: $$ \begin{aligned} \frac{\log \frac{1}{p(X_1, \dots, X_n)}}{n} &\to H(X) &\text{[In probability]} \end{aligned} $$ Because(proof): $$ \begin{aligned} \frac{\log \frac{1}{p(X_1, \dots, X_n)}}{n} &= \frac{\sum_{i=1}^{n} \log \frac{1}{p(X_i)}}{n} \\ &\to E \left[ \log \frac{1}{p(X)} \right] = H(X) &\text{[In probability]} \end{aligned} $$

Typical Set

The typical set $ A_{\epsilon}^{(n)} $ is a set of $ (x_1, \dots, x_n) \in \mathcal{X}^{n} $ that satisfies:

$$ \begin{aligned} 2^{-n[H(X) + \epsilon]} \leq p(x_1, \dots, x_n) \leq 2^{-n[H(X) - \epsilon]} \end{aligned} $$

Step I

It is obviously:

$$ \begin{aligned} H(X) - \epsilon \leq \frac{\log \frac{1}{p(x_1, \dots, x_n)}}{n} \leq H(X) + \epsilon \end{aligned} $$

Step II

By AEP:

$$ \begin{aligned} \forall \delta > 0, \exists n_0, n \geq n_0, \\ P \left[ \left|\frac{\log \frac{1}{p(x_1, \dots, x_n)}}{n} - H(X) \right| < \epsilon \right] &> 1 - \delta &\text{[In probability]} \end{aligned} $$

Let $ \delta = \epsilon $:

$$ \begin{aligned} P \left[ A_{\epsilon}^{(n)} \right] &> 1 - \epsilon \end{aligned} $$

Step III

The size of the typical set $ A_{\epsilon}^{(n)} $:

$$ \begin{aligned} (1 - \epsilon) 2^{n[H(X) - \epsilon]} \leq |A_{\epsilon}^{(n)}| \leq 2^{n[H(X) + \epsilon]} \end{aligned} $$

Because(proof):

$$ \begin{aligned} 1 = \sum_{\underline{x} \in \mathcal{X}^n} p(\underline{x}) \geq \sum_{\underline{x} \in A_{\epsilon}^{(n)}} p(\underline{x}) &\geq \sum_{\underline{x} \in A_{\epsilon}^{(n)}} 2^{-n[H(X) + \epsilon]} \\ &= |A_{\epsilon}^{(n)}| \cdot 2^{-n[H(X) + \epsilon]} \end{aligned} $$

and:

$$ \begin{aligned} 1 - \epsilon < P \left[ A_{\epsilon}^{(n)} \right] = \sum_{\underline{x} \in A_{\epsilon}^{(n)}} p(\underline{x}) &\leq \sum_{\underline{x} \in A_{\epsilon}^{(n)}} 2^{-n[H(X) - \epsilon]} \\ &= |A_{\epsilon}^{(n)}| \cdot 2^{-n[H(X) - \epsilon]} \end{aligned} $$

by Jon